package problems;

import java.util.List;

import utils.Utils;

public class Problem234 extends Problem<Long> {
	private final long TARGET = 999966663333L;
	private final List<Integer> sieve = Utils.sieve(1000000); 

	public static void main(String[] args) {
		Problem234 problem234 = new Problem234();
		problem234.runTimed();
		problem234.printResult();
	}

	@Override
	public void run() {
		//Takes way too long, ~3*10^9 sec = ~100 years
		long sum = 0;
		for (long i = 4; i <= TARGET; i++) {
			if (isSemiDivisible(i)) {
				sum += i;
				if (sum < 0L) {
					throw new IllegalStateException("Overflow!");
				}
			}
		}
		setResult(sum);
	}

	private boolean isSemiDivisible(long i) {
		int sqrt = (int)Math.sqrt(i);
		final int lps = findPrimeLower(sqrt);
		final int ups;
		if (sqrt*sqrt != i) {
			ups = findPrimeUpper(sqrt+1);
		}
		else {
			ups = findPrimeUpper(sqrt);
		}
		return i % lps == 0 ^ i % ups == 0;
	}

	private int findPrimeLower(int n) {
		for (;;n--) {
			if (sieve.contains(n)) {
				return n;
			}
		}
	}

	private int findPrimeUpper(int n) {
		for (;;n++){
			if (sieve.contains(n)) {
				return n;
			}
		}
	}
}
